#include "CalculTrajet.h"

/**
 * \fn       void initCalcTraj(CalculTrajet* calcTraj)
 * \brief    initialise les valeurs d'une structure CalculTrajet.
 *
 * \param    calcTraj    pointeur sur une structure CalculTrajet à initialiser
 */
void initCalcTraj(CalculTrajet* calcTraj)
{
  calcTraj->caseCarte = NULL;
  calcTraj->coutDepAct = 0;
  calcTraj->coutActDest = 0;
  calcTraj->coutSomme = 0;
  calcTraj->xArr = 0;
  calcTraj->yArr = 0;
  calcTraj->parent = NULL;
  calcTraj->calcSuivant = NULL;
  calcTraj->calcPrecedent = NULL;
  calcTraj->nbElements = 0;
}

/**
 * \fn       void creerCalcTraj(CalculTrajet** calcTraj)
 * \brief    alloue une structure CalculTrajet dans la mémoire.
 *
 * \param    calcTraj    adresse d'un pointeur sur une structure CalculTrajet à allouer
 */
void creerCalcTraj(CalculTrajet** calcTraj)
{
  *calcTraj = (CalculTrajet*) malloc(sizeof(CalculTrajet));
  initCalcTraj(*calcTraj);
}


void setCalcTraj(CalculTrajet* calcTraj, Carte* carte, int xDep, int yDep, int zDep, int xArr, int yArr)
{
  calcTraj->caseCarte = getCaseCarte(carte, xDep, yDep, zDep);
  calcTraj->xArr = xArr;
  calcTraj->yArr = yArr;
}

/**
 * \fn       static int calculDistance(int xDep, int yDep, int xArr, int yArr)
 * \brief    calcule le carré de la distance euclidienne entre deux points
 *
 * \param   xDep    coordonnée x de départ du chemin mesuré
 * \param   yDep    coordonnée y de départ du chemin mesuré
 * \param   xArr    coordonnée x d'arrivée du chemin mesuré
 * \param   yArr    coordonnée y d'arrivée du chemin mesuré
 */
static int calculDistance(int xDep, int yDep, int xArr, int yArr)
{
  return ((xDep-xArr)*(xDep-xArr) + (yDep-yArr)*(yDep-yArr));
}

/**
 * \fn       static char dejaDansListe(Case* caseAVerif, CalculTrajet* trajet)
 * \brief    vérifie si la case donnée en argument est déja dans la liste donnée en argument et renvois 1 si c'est le cas, 0 sinon
 * \param    caseAVerif   pointeur sur la case à vérifier
 * \param    trajet       pointeur sur le trajet dans lequel chercher caseAVerif
 */
static char dejaDansListe(Case* caseAVerif, CalculTrajet* trajet, CalculTrajet** emplacementDansListe)
{
  CalculTrajet* tmp;

  tmp = trajet;

  do
    {
      if(tmp->caseCarte != NULL)
	{
	  /*printf("compare x: %d %d, y: %d %d z: %d %d\n",caseAVerif->x,trajet->caseCarte->x,caseAVerif->y,tmp->caseCarte->y,caseAVerif->z,tmp->caseCarte->z);*/
      
	  if ((caseAVerif->x == tmp->caseCarte->x) && (caseAVerif->y == tmp->caseCarte->y) && (caseAVerif->z == tmp->caseCarte->z))
	    {
	      *emplacementDansListe = trajet;
	      return 1;
	    }
	}
      
      if(tmp->calcPrecedent != NULL)
	tmp = tmp->calcPrecedent;
    } while(tmp->calcPrecedent != NULL);

  return 0;
}


/**
 * \fn       void ajoutCasesAdjacentes(CalculTrajet* listeOuverte, const CalculTrajet* listeFermee, CalculTrajet* dernièreCaseCarte)
 * \brief    ajoute les cases adjacentes à la liste ouverte
 * \details  ajoute les cases adjacentes à la liste ouverte en vérifiant si ceux-ci sont franchissables
 * \param    listeOuverte   liste dans laquelle seront ajoutées les cases valides pour être testées pour la création du chemin
 * \param    listeFermee    trajet déja validé jusqu'a maintenant et dans lequel la future case ajoutée ne doit pas se trouver
 * \param    caseAtuelle    case actuelle autours de laquelle vont être récupérées les cases adjacentes
 */
void ajoutCasesAdjacentes(Carte* carte, CalculTrajet** listeOuverte, CalculTrajet* listeFermee)
{
  int i,j,z,xMax,yMax;
  CalculTrajet* calcTmp;
  CalculTrajet* emplacementTmp;
  
  xMax = getXCarte(carte) - 1;
  yMax = getYCarte(carte) - 1;
  z = listeFermee->caseCarte->z;
  creerCalcTraj(&calcTmp);
  calcTmp->xArr = listeFermee->xArr;
  calcTmp->yArr = listeFermee->yArr;

  creerCalcTraj(&emplacementTmp);
  emplacementTmp->xArr = listeFermee->xArr;
  emplacementTmp->yArr = listeFermee->yArr;


  /* on met tous les noeud adjacents dans la liste ouverte (+vérif) */
  for (i = (listeFermee->caseCarte->x)-1; i<=(listeFermee->caseCarte->x)+1; i++){
    if ((i<0) || (i>=xMax))  /* si pas en dehors des limites x*/
      continue;
    for (j = (listeFermee->caseCarte->y)-1; j<=(listeFermee->caseCarte->y)+1; j++){
     
      if ((j<0) || (j>=yMax))   /* si pas en dehors des limites y*/
	continue;
      if ((i==(listeFermee->caseCarte->x)) && (j==(listeFermee->caseCarte->y)))  /*si pas la case actuelle*/
	{                
	  continue;
	}
      else
	{
	  calcTmp->caseCarte = getCaseCarte(carte, i, j, z);


	  if(calcTmp->caseCarte == NULL || getTraversableCase(calcTmp->caseCarte) == 0) /*terrain franchissable*/
	    continue;

	  if (dejaDansListe(calcTmp->caseCarte, listeFermee, &emplacementTmp) == 0) /*case n'est pas déja dans liste fermee*/
	    {
	      calcTmp->coutDepAct = listeFermee->coutDepAct + calculDistance(i,j,(listeFermee->caseCarte->x),(listeFermee->caseCarte->y));
	      calcTmp->coutActDest = calculDistance(i,j,listeFermee->xArr,listeFermee->yArr);
	      calcTmp->coutSomme = calcTmp->coutDepAct + calcTmp->coutActDest;
	      calcTmp->parent = listeFermee;
	    
	      if(dejaDansListe(calcTmp->caseCarte, *listeOuverte, &emplacementTmp) != 0)
		{
		  if(calcTmp->coutSomme < emplacementTmp->coutSomme) /*si c'est un meilleur chemin on change*/
		    {
		      emplacementTmp->coutDepAct = calcTmp->coutDepAct;
		      emplacementTmp->coutActDest= calcTmp->coutActDest;
		      emplacementTmp->coutSomme = calcTmp->coutSomme;
		      emplacementTmp->parent = calcTmp->parent;
		    }
		}
	      else
		{
		  calcTmp->calcPrecedent = *listeOuverte;
		  (*listeOuverte)->calcSuivant = calcTmp;
		  *listeOuverte = (*listeOuverte)->calcSuivant;
		  creerCalcTraj(&calcTmp);
		}
	    }
	}
    }
  }
  /*  printf("aff1.5 x:%d y:%d\n\n",(*listeOuverte)->caseCarte->x,(*listeOuverte)->caseCarte->y);*/

}

/**
 * \fn       CalculTrajet* meilleureCase(const CalculTrajet* listeOuverte)
 * \brief    renvois un pointeur sur la meilleure case de calcul de la liste ouverte
 * \details  compare les score des cases de la liste ouverte afin de renvoyer un pointeur sur celle de score optimale
 * \param    listeOuverte   pointeur sur la liste ouverte à tester
 */
CalculTrajet* meilleureCase(CalculTrajet* listeOuverte)
{
  CalculTrajet* tmp;
  CalculTrajet* resultat;

  resultat = listeOuverte;
  tmp = listeOuverte;

  /*printf("coutdep res:%d\n",resultat->coutSomme);*/

  while(tmp->caseCarte != NULL && tmp->coutSomme != 0)
    {
      if(tmp->coutSomme < resultat->coutSomme)
	{
	  resultat = tmp;
	}
      tmp = tmp->calcPrecedent;
    }
  return resultat;
}

/**
 * \fn       void ajouterListeFermee(CalculTraj* listeFermee, Case* caseAjout)
 * \brief    ajoute une case à la liste fermée afin de constituer le trajet final
 * \param    listeFermee   pointeur sur la liste fermée
 * \param    caseAjout     pointeur sur la case à ajouter
 */
void ajouterListeFermee(CalculTrajet** listeFermee, CalculTrajet** listeOuverte, CalculTrajet* calcAjout)
{
  CalculTrajet* tmp;
  int nbElements;

  /*suppression du noeud de la liste ouverte*/
  if(calcAjout->calcSuivant != NULL)
    {
      tmp = calcAjout->calcPrecedent;
      tmp->calcSuivant = calcAjout->calcSuivant;
      tmp = calcAjout->calcSuivant;
      tmp->calcPrecedent = calcAjout->calcPrecedent;
    }
  else
    {
      tmp = calcAjout->calcPrecedent;
      tmp->calcSuivant = NULL;
      *listeOuverte = tmp;
    }

  /*insertion dans la liste fermee*/
  nbElements = (*listeFermee)->nbElements;
  calcAjout->xArr = (*listeFermee)->xArr;
  calcAjout->yArr = (*listeFermee)->yArr;
  calcAjout->calcPrecedent = *listeFermee;
  (*listeFermee)->calcSuivant = calcAjout;
  *listeFermee = (*listeFermee)->calcSuivant;
  (*listeFermee)->nbElements = nbElements+1;
  (*listeFermee)->calcSuivant = NULL;
}
/**
 * \fn       void ordonneChemin(const CalculTrajet* listeFermee, CalculTrajet* listeTriee)
 * \brief    renvois une liste de case allant du départ du trajet à l'arrivée
 * \details  comme la liste fermée une fois générée se trouve dans l'ordre de l'arrivée au départ, cette fonction retourne celle-ci
 * \param    listeFermee   pointeur sur la liste fermée
 * \param    listeTriee    pointeur sur la liste dans l'ordre correct
 */
void ordonneChemin(CalculTrajet* listeFermee, CalculTrajet** listeTriee)
{
  int nbElements;
  CalculTrajet* tmp;

  nbElements = listeFermee->nbElements;

  do
    {
      listeFermee->nbElements = nbElements;
      if(listeFermee->parent != NULL)
	{
	  tmp = listeFermee;
	  listeFermee = listeFermee->parent;
	  listeFermee->calcSuivant = tmp;
	}
    }  while(listeFermee->parent != NULL);

  *listeTriee = listeFermee;

}

static void concateneChemins(CalculTrajet** cheminPrincipal, CalculTrajet** cheminAConcatener)
{
  CalculTrajet* tmp;
  if((*cheminPrincipal)->caseCarte == NULL)
    {
      *cheminPrincipal = *cheminAConcatener;
    }
  else
    {
      tmp = *cheminPrincipal;
      while(tmp->calcSuivant != NULL)
	{
	  tmp = tmp->calcSuivant;
	}
      tmp->calcSuivant = *cheminAConcatener;
    }
}

/**
 * \fn       void recherchePortionChemin(Carte* carte, int xDep, int yDep, int xArr, int yArr, int zChemin, Carte* carte)
 * \brief    applique l'algorithme A* dans une portion de chemin limitée à un étage
 * \param    carte      pointeur sur la carte de jeu
 * \param   xDep    coordonnée x de départ du chemin mesuré
 * \param   yDep    coordonnée y de départ du chemin mesuré
 * \param   xArr    coordonnée x d'arrivée du chemin mesuré
 * \param   yArr    coordonnée y d'arrivée du chemin mesuré
 * \param   zChemin profondeur de la portion actuelle
 * \param   portionTrajet  trajet de la portion désirée
 */
void recherchePortionChemin(Carte* carte, int xDep, int yDep, int xArr, int yArr, int zChemin, CalculTrajet** portionTrajet)
{
  int i;
  CalculTrajet* listeFermee;
  CalculTrajet* listeOuverte;
  CalculTrajet* tmp;

  i = 0;

  creerCalcTraj(&listeFermee);
  creerCalcTraj(&listeOuverte);

  setCalcTraj(listeFermee,carte, xDep,yDep,zChemin,xArr,yArr);
  setCalcTraj(listeOuverte,carte,xDep,yDep,zChemin,xArr,yArr);


  /*premier cycle*/
  ajoutCasesAdjacentes(carte, &listeOuverte, listeFermee);

  tmp = meilleureCase(listeOuverte);
  
  ajouterListeFermee(&listeFermee, &listeOuverte, tmp);
   

  /* boucle du cycle*/
  
  while(!(listeFermee->caseCarte->x == listeFermee->xArr && listeFermee->caseCarte->y == listeFermee->yArr) 
	&& !(listeOuverte->calcSuivant == NULL && listeOuverte->calcPrecedent == NULL)
	&& i < 100)
    {
      ajoutCasesAdjacentes(carte, &listeOuverte, listeFermee);

      tmp = meilleureCase(listeOuverte);

      ajouterListeFermee(&listeFermee,&listeOuverte, tmp);

      tmp = listeOuverte;
      do
	{
	  if(tmp == NULL)
	    printf("Erreur, case nulle");
	 
	  if(tmp->calcPrecedent != NULL)
	    tmp = tmp->calcPrecedent;
	}   while(tmp->calcPrecedent != NULL);

      i++;
    }

  ordonneChemin(listeFermee,portionTrajet);

  free(listeOuverte);
}

/**
 * \fn        int rechercheCoordonneeEscalier(const int zDep, const int zArr, const int xDep, const int yDep, int* xEscalier, int* yEscalier,Carte* carte)
 * \brief    applique l'algorithme A* dans une portion de chemin limitée à un étage
 * \param   zDep    coordonnée z de l'étage de départ
 * \param   zArr    coordonnée z de l'étage d'arrivée
 * \param   xDep    coordonnée x de départ
 * \param   yDep    coordonnée y de départ
 * \param   xEscalier    coordonnée x de l'escalier
 * \param   yEscalier    coordonnée y de l'escalier
 * \param   carte   pointeur sur la carte de jeu
 */
int rechercheCoordonneeEscalier(const int zDep, const int zArr, const int xDep, const int yDep, int* xEscalier, int* yEscalier,Carte* carte)
{
  Case* tmp1;
  Case* tmp2;

  unsigned int x = xDep;
  unsigned int y = yDep;
  int pas = 1;
  int i,j,nbActuel;
  unsigned int xMax, yMax, zMax; /* coordonnées maximales pour la case à changer */

  char hautDroit = 'o'; /* équivalent booléen : est-on en train d'aller vers
			   le haut ou vers la droite ? Si oui, hautDroit vaut o ;
			   si non, hautDroit vaut n */

  nbActuel = 0;

  xMax = getXCarte(carte) - 1;
  yMax = getYCarte(carte) - 1;
  zMax = getZCarte(carte) -1;

  if((x > 0) && (x < xMax) && (y > 0) && (y < yMax) && (y < yMax)  && (zDep >= 0) && (zDep < zMax) && (zArr >= 0) && (zArr < zMax))
    {
      tmp1 = getCaseCarte(carte, x, y, zDep);
      tmp2 = getCaseCarte(carte, x, y, zArr);
      
      if( (getTraversableCase(tmp1) == 1) && (getTraversableCase(tmp2) == 1) )
	{
	  *xEscalier = x;
	  *yEscalier = y;
	  return 1;
	}	
    }

  /* Parcours en spirale autour de la graine et modification le cas échéant */
  while(nbActuel < 200)
    {
      /* On monte ou on descend */
      for(i=0;i<pas;i++)
	{
	  if(hautDroit == 'o')
	    {
	      x--;
	    }
	  else
	    {
	      x++;
	    }
	  
	  if((x > 0) && (x < xMax) && (y > 0) && (y < yMax) && (zDep > 0) && (zDep < zMax) && (zArr >= 0) && (zArr < zMax))
	    {
	      tmp1 = getCaseCarte(carte, x, y, zDep);
	      tmp2 = getCaseCarte(carte, x, y, zArr);


	      if( (getTraversableCase(tmp1) == 1) && (getTraversableCase(tmp2) == 1) )
		{
		  *xEscalier = x;
		  *yEscalier = y;
		  return 1;
		}	  
	    }
	}
	  
      /* on va à droite ou à gauche */
      for(j=0; j<pas; j++)
	{

	  if(hautDroit == 'o')
	    {
	      y++;
	    }
	  else
	    {
	      y--;
	    }


	  if((x > 0) && (x < xMax) && (y > 0) && (y < yMax) && (y < yMax)  && (zDep >= 0) && (zDep < zMax) && (zArr >= 0) && (zArr < zMax))
	    {
	      tmp1 = getCaseCarte(carte, x, y, zDep);
	      tmp2 = getCaseCarte(carte, x, y, zArr);

	      if( (getTraversableCase(tmp1) == 1) && (getTraversableCase(tmp2) == 1) )
		{
		  *xEscalier = x;
		  *yEscalier = y;
		  return 1;
		}	
	    }
			   
	}
      pas++;

      if(hautDroit == 'o')
	{
	  hautDroit = 'n';
	}
      else
	{
	  hautDroit = 'o';
	}
      nbActuel++;

    }
  return 0;

}


/**
 * \fn      void rechercheChemin(int xDep, int yDep, int zDep, int xArr, int yArr, int zArr, Carte* carte) 
 * \brief    applique l'algorithme A* pour trouver le chemin entre deux points donnés
 * \details  si le chemin est calculé sur plusieurs niveaux celui-ci sera divisé en portion entre les escalier entre étages
 * \param   xDep    coordonnée x de départ du chemin mesuré
 * \param   yDep    coordonnée y de départ du chemin mesuré
 * \param   zDep    coordonnée z de départ du chemin mesuré
 * \param   xArr    coordonnée x d'arrivée du chemin mesuré
 * \param   yArr    coordonnée y d'arrivée du chemin mesuré
 * \param   zArr    coordonnée z d'arrivée du chemin mesuré
 * \param   carte   pointeur sur la carte de jeu
 */
CalculTrajet* rechercheChemin(int xDep, int yDep, int zDep, int xArr, int yArr, int zArr, Carte* carte)
{
  int i;
  int booleen;

  int xEscalier;
  int yEscalier;
  int xTmpDep,yTmpDep,zTmpDep;

  CalculTrajet* chemin = NULL;
  CalculTrajet* portionChemin = NULL;

  xEscalier = xDep;
  yEscalier = yDep;

  xTmpDep = xDep;
  yTmpDep = yDep;
  zTmpDep = zDep;

  creerCalcTraj(&chemin);

  if(zDep == zArr)
    {
      recherchePortionChemin(carte,xDep,yDep,xArr,yArr,zDep,&chemin);
      return chemin;
    }
  else
    {
      if(zTmpDep < zArr)
	{
	  for(i=zDep;i<zArr;i++)
	    {
	      
	      booleen = rechercheCoordonneeEscalier(zTmpDep, (zTmpDep+1), xArr, yArr, &xEscalier, &yEscalier,carte);

 
	      if(booleen == 1)
		{
		  recherchePortionChemin(carte,xTmpDep,yTmpDep,xEscalier,yEscalier,zTmpDep,&portionChemin);		  
		  concateneChemins(&chemin,&portionChemin);
		  xTmpDep = xEscalier;
		  yTmpDep = yEscalier;
		  zTmpDep++;
		}
	      else
		{
		 recherchePortionChemin(carte,xTmpDep,yTmpDep,xArr,yArr,zTmpDep,&portionChemin);
		 concateneChemins(&chemin,&portionChemin);
	  
		 return chemin;
		}
	    }
  

	  if(xTmpDep != xArr || yTmpDep != yArr)
	    recherchePortionChemin(carte,xTmpDep,yTmpDep,xArr,yArr,zTmpDep,&portionChemin);
	 
	  else
	    {
	      portionChemin = (CalculTrajet*) malloc(sizeof(CalculTrajet));
	      portionChemin->caseCarte = getCaseCarte(carte,xArr,yArr,zTmpDep);
	    } 

	  concateneChemins(&chemin,&portionChemin);
	  return chemin;
	}
      else
	{
	  for(i=zDep;i>zArr;i--)
	    {

	      booleen = rechercheCoordonneeEscalier(zTmpDep, (zTmpDep-1), xArr, yArr, &xEscalier, &yEscalier,carte);
	      if(booleen == 1)
		{
		  recherchePortionChemin(carte,xTmpDep,yTmpDep,xEscalier,yEscalier,zTmpDep,&portionChemin);
		  concateneChemins(&chemin,&portionChemin);
		  xTmpDep = xEscalier;
		  yTmpDep = yEscalier;
		  zTmpDep--;
		}
	      else
		{
		  recherchePortionChemin(carte,xTmpDep,yTmpDep,xArr,yArr,zTmpDep,&portionChemin);
		  concateneChemins(&chemin,&portionChemin);
		  return chemin;
		}
	    }


	  if(xTmpDep != xArr || yTmpDep != yArr)
	    recherchePortionChemin(carte,xTmpDep,yTmpDep,xArr,yArr,zTmpDep,&portionChemin);
	 
	  else
	    {
	      portionChemin = (CalculTrajet*) malloc(sizeof(CalculTrajet));
	      portionChemin->caseCarte = getCaseCarte(carte,xArr,yArr,zTmpDep);
	    } 

	  concateneChemins(&chemin,&portionChemin);
	  return chemin;
	}

    }
  return chemin;

}


/*===================== tests ===================*/


static void carteTest(Carte** carteTest)
{
  TabTerrains tableauTerr;
  char *fichierDat = {"DatTerr"};

  tableauTerr = creerTabTerrains(fichierDat);

  *carteTest = genererCarte(100,100,5,6,8,80,20,&tableauTerr);
       
}
/**
 * \fn       void testCalcTraj()
 * \brief    teste le module CalculTrajet
 */
void testCalculTrajet()
{
  /* int distance; */
  Carte* carte;
  CalculTrajet* listeFermee;
  CalculTrajet* listeOuverte;
  /*CalculTrajet* listeTriee;*/
  CalculTrajet* tmp;

  carteTest(&carte);  

  creerCalcTraj(&listeFermee);
  creerCalcTraj(&listeOuverte);

  setCalcTraj(listeFermee,carte, 2,2,0,8,8);

  /*setCalcTraj(listeOuverte,carte, 2,2,0,8,8);*/
  /*
 
    ajoutCasesAdjacentes(carte, &listeOuverte, listeFermee);

    tmp = listeOuverte;

    printf("aff2 x:%d y:%d\n",listeOuverte->caseCarte->x,listeOuverte->caseCarte->y);

    printf("Trajet :\n");
    distance = calculDistance(2,2,8,8);
    printf("distance totale:%d\n",distance);
    printf("Liste Ouverte:\n");
    printf("xArr:%d yArr:%d\n",tmp->xArr,tmp->yArr);

    while(tmp->caseCarte != NULL)
    {
    printf("x:%d y:%d cout1:%d cout2:%d cout3:%d\n\n",tmp->caseCarte->x,tmp->caseCarte->y,tmp->coutDepAct,tmp->coutActDest,tmp->coutSomme);
    tmp = tmp->calcPrecedent;
    }

    printf("Meilleure case:\n");
    tmp = meilleureCase(listeOuverte);
    ajouterListeFermee(&listeFermee, listeOuverte, tmp);


    printf("x:%d y:%d cout1:%d cout2:%d cout3:%d\n\n",tmp->caseCarte->x,tmp->caseCarte->y,tmp->coutDepAct,tmp->coutActDest,tmp->coutSomme);



    tmp = listeFermee;  

    printf("Liste fermée:\n");
    do
    {
    printf("x:%d y:%d\n",tmp->caseCarte->x,tmp->caseCarte->y);
    tmp = tmp->calcPrecedent;
    }  while(tmp != NULL);

  */
  /* reste cycle*/
  /*
    while(listeFermee->caseCarte->x != listeFermee->xArr || listeFermee->caseCarte->y != listeFermee->yArr)
    {
    ajoutCasesAdjacentes(carte, &listeOuverte, listeFermee);
    tmp = meilleureCase(listeOuverte);
    ajouterListeFermee(&listeFermee, listeOuverte, tmp);
    }


    tmp = listeFermee;  

    printf("Liste fermée:\n");
    do
    {
    printf("x:%d y:%d\n",tmp->caseCarte->x,tmp->caseCarte->y);
    tmp = tmp->calcPrecedent;
    }  while(tmp != NULL);
  */
  /*
    recherchePortionChemin(carte,2,2,60,10,0,&listeTriee);

    tmp = listeTriee;  

    printf("Liste triée:\n");

    do
    {
    if(tmp == NULL)
    printf("Erreur, case nulle");

    printf("x:%d y:%d\n",tmp->caseCarte->x,tmp->caseCarte->y);
    if(tmp->calcSuivant != NULL)
    tmp = tmp->calcSuivant;
    }   while(tmp->calcSuivant != NULL);
  */
  /* recherchePortionChemin(carte,2,2,92,54,0,&listeTriee);

     tmp = listeTriee;  */

  tmp = rechercheChemin(2,2,0,92,54,0,carte);

  printf("Liste triée:\n");

  do
    {
      if(tmp == NULL)
	printf("Erreur, case nulle");

      printf("x:%d y:%d\n",tmp->caseCarte->x,tmp->caseCarte->y);
      if(tmp->calcSuivant != NULL)
	tmp = tmp->calcSuivant;
    }   while(tmp->calcSuivant != NULL);
 

  detruireCarte(carte);
  free(listeFermee);
  free(listeOuverte);
  free(tmp);

  printf("Fin du test du calcul de trajet\n");

}
